/*****************************************************************************/
// This file is part of Hikari3D.
// 
// Hikari3D is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// 
// Hikari3D is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with Foobar.  If not, see <http://www.gnu.org/licenses/>.
//
// Copyright 2008 Sebastian Pick
/*****************************************************************************/

#ifndef __BTREE_H
#define __BTREE_H

// === Includes ============================================================ //
#include <iostream>
#include <vector>

using namespace std;


// === Class Declarations ================================================== //
//! This class implements a single node of a bayer tree.
template<typename key_type, typename value_type>
class CBTreeNode
{
// This is because the tree needs to have access to the private constructor.
template <typename K, typename V> friend class CBTree;

public:
	// --- Constructors/Destructor ----------------------------------------- //
	//! Use this constructor to create new nodes/leaves.
	/*!
		\param key The key of the new node. It will be used to determine
				   the nodes position in the tree.
		\param value The value of the new node.
	 */
	inline CBTreeNode(const key_type &key, const value_type &value);
	

	// --- Interface ------------------------------------------------------- //
	//! Prints the node's key to the console.
	/*!
		\param bPrintRelatives In order to automatically invoke print calls
							   on the sibling and child, too, this has to be
							   set to true. Relatives will be printed with
							   bPrintRelatives set to 'true' as well,
							   hence the whole sub-tree of this node will
							   be printed.
	 */
	inline void Print(bool bPrintRelatives=false);


	// --- Selectors ------------------------------------------------------- //
	//! Selector for getting the parent of the node.
	/*!
		There is no setter for the same reason as for the key selectors.
	 */
	inline CBTreeNode<key_type, value_type>* GetParent() const;


	//! Selector for getting the children of the node.
	inline vector< CBTreeNode<key_type, value_type>* >* GetChildren();


	//! Selector for getting the key.
	/*!
		Setting the key is not supported/public because changing the key of
		elements that already have been inserted into a tree will possibly
		violate the insertion rules.
	 */
	inline key_type GetKey() const;


	//! Selectors for setting/getting the node's value.
	inline bool SetValue(const value_type &value);
	inline value_type GetValue();
	

protected:
	// --- Variables ------------------------------------------------------- //
	CBTreeNode<key_type, value_type> *m_pParent;

	vector< CBTreeNode<key_type, value_type>* > m_vChildren;

	key_type				m_oKey;
	value_type				m_oValue;

	bool					m_bIsLeaf;


private:
	//! This constructor will create a new (inner) node.
	/*!
		NOTE: In order to successfully insert a new node into a tree
			  the last parameter (bIsLeaf) must be true.
			  So it is recommended that users only using the tree itself
			  never touch this parameter.

		\param key The key of the node. It will be used to determine
				   the nodes position in the tree.
	 */
	inline CBTreeNode(const key_type &key);

	//! Selector for setting the Parent.
	inline bool SetParent(CBTreeNode<key_type, value_type> *pParent);


	//! Selector for setting the key.
	/*!
		After all this is a necessary operation for nodes (!leaves) since
		their key will actually change frequently over time, i.e.
		whenever the structure of the tree will have to be updated.
		Therefore a check will be performed whether the node on which this
		operation is executed actually is a leaf or not.
	 */
	inline bool SetKey(const key_type &key);

	inline void Print(bool bPrintRelatives, int iLevel);
};


// === Inline Functions ==================================================== //
template<typename K, typename V>
CBTreeNode<K, V>::CBTreeNode(const K &key, const V &value)
	: m_pParent(NULL), m_oKey(key), m_oValue(value), m_bIsLeaf(true)
{
}

template<typename K, typename V>
CBTreeNode<K, V>::CBTreeNode(const K &key)
	: m_pParent(NULL), m_oKey(key), m_bIsLeaf(false)
{
}

template<typename K, typename V>
void CBTreeNode<K, V>::Print(bool bPrintRelatives)
{
	this->Print(bPrintRelatives, 0);
}

template<typename K, typename V>
void CBTreeNode<K, V>::Print(bool bPrintRelatives, int iLevel)
{
	for(int i=0; i<iLevel; ++i)
		if(i == iLevel-1)
			cout << "|-";
		else
			cout << "| ";

	cout << m_oKey;
	if(GetParent())
		cout << " (" << GetParent()->GetKey() << ")";
	if(m_bIsLeaf)
		cout << " *";
	cout << endl;

	for(int i=0; i<(int)GetChildren()->size(); ++i)
		GetChildren()->at(i)->Print(bPrintRelatives, iLevel+1);

}

template<typename K, typename V>
bool CBTreeNode<K, V>::SetParent(CBTreeNode<K, V> *pParent)
{
	m_pParent = pParent;

	return true;
}

template<typename K, typename V>
CBTreeNode<K, V>* CBTreeNode<K, V>::GetParent() const
{
	return m_pParent;
}

template<typename K, typename V>
vector< CBTreeNode<K, V>* >* CBTreeNode<K, V>::GetChildren()
{
	return &m_vChildren;
}

// This function is private.
template<typename K, typename V>
bool CBTreeNode<K, V>::SetKey(const K &key)
{
	if(m_bIsLeaf)
		return false;

	m_oKey = key;

	return true;
}

template<typename K, typename V>
K CBTreeNode<K, V>::GetKey() const
{
	return m_oKey;
}

template<typename K, typename V>
bool CBTreeNode<K, V>::SetValue(const V &value)
{
	m_oValue = value;

	return true;
}

template<typename K, typename V>
V CBTreeNode<K, V>::GetValue()
{
	return m_oValue;
}


// ========================================================================= //


// === Class Declaration =================================================== //
//! This class implements a bayer tree.
template<typename key_type, typename value_type>
class CBTree
{
public:
	// --- Constructors/Destructor ----------------------------------------- //
	//! Just the standard constructor.
	inline CBTree();


	//! The destructor.
	~CBTree();


	// --- Interface ------------------------------------------------------- //
	//! This function performs the tree setup, like setting its "dimensions".
	/*!
		NOTE: Mind that the following holds: iMaxNodes <= 2 * iMinNodes - 1.
			  If this does not hold, 'false' will be returned!

		\param iMinNodes The minimum number of children for each leaf.
		\param iMaxNodes The maximum number of children for each leaf.
		\return 'True' iff the tree is ready to be used.
	 */
	bool Init(int iMinNodes, int iMaxNodes);


	//! Add new elements to the tree using this function.
	/*!
		\param elem The element to be added.
		\return 'True' iff the element was added successfully.
	 */
	bool Insert(const key_type &key, const value_type &value);


	//! Delete the element with the specified key from the tree.
	/*!
		\param key The key of the element to be deleted.
		\return 'True' iff the element was found AND removed.
	 */
	bool Delete(const key_type &key);


	//! Retrieve single elements via this function.
	/*!
		\param key The key of the element to be retrieved.
		\return A pointer to the element in the node. 
				Or NULL if none was found.
	 */
	value_type Search(const key_type &key) const;


	//! Prints the tree to the console.
	inline void Print(bool bPrintStructure = true) const;


	//! Retrieve the current height of the tree.
	inline int GetTreeHeight() const;


	//! Retrieve the current number of elements in the tree.
	inline int GetNumberOfElements() const;


protected:
	// --- Variables ------------------------------------------------------- //
	bool				m_bIsInited;

	int					m_iMinNodes,
						m_iMaxNodes,
						m_iTreeHeight,
						m_iNumElements;

	CBTreeNode<key_type, value_type>
						*m_pRootNode;

	int					m_iTraverseHelper;

private:
	void CleanUp(CBTreeNode<key_type, value_type> *pNode);
};


// ************************************************************************* //
// ** Inline function definitions 
// ************************************************************************* //

template<typename K, typename V>
CBTree<K, V>::CBTree()
	: m_bIsInited(false), m_pRootNode(NULL),
	  m_iTreeHeight(0), m_iNumElements(0)
{
}

template<typename K, typename V>
void CBTree<K, V>::Print(bool bPrintStructure) const
{
	if(!m_bIsInited)
		return;
	
	cout << endl;
	cout << "------------------------------------------------------------"
		<< endl;

	cout << "(" << m_iMinNodes << ", " << m_iMaxNodes << ")-Tree" << 
		" with " << m_iNumElements << " elements and " << m_iTreeHeight <<
		" levels." << endl << endl;

	cout << "Tree structure: " << endl;
	
	if(m_pRootNode && bPrintStructure) {
		cout << endl;
		m_pRootNode->Print(true);
	}
	else if(!m_pRootNode)
		cout << "The tree is empty." << endl;
	else
		cout << "Printing tree structure omitted." << endl;
	
	cout << "------------------------------------------------------------"
		<< endl;
	cout << endl;
}

template<typename K, typename V>
int CBTree<K, V>::GetTreeHeight() const
{
	return m_iTreeHeight;
}

template<typename K, typename V>
int CBTree<K, V>::GetNumberOfElements() const
{
	return m_iNumElements;
}

// === Destructor ========================================================== //
template<typename K, typename V>
CBTree<K, V>::~CBTree()
{
	if(m_pRootNode)
		CleanUp(m_pRootNode);
}


// === Implementation ====================================================== //
template<typename K, typename V>
void CBTree<K, V>::CleanUp(CBTreeNode<K, V> *pNode)
{
	if(pNode->GetChildren()->size() == 0)
		delete pNode;
	else
		for(int i=0; i<(int)pNode->GetChildren()->size(); ++i)
			CleanUp(pNode->GetChildren()->at(i));
	
	return;
}

template<typename K, typename V>
bool CBTree<K, V>::Init(int iMinNodes, int iMaxNodes)
{
	if(iMinNodes <= 1 || iMaxNodes > 2 * iMinNodes - 1)
		return false;

	m_iMinNodes = iMinNodes;
	m_iMaxNodes = iMaxNodes;
	
	if(m_pRootNode)
		CleanUp(m_pRootNode);	

	m_iTreeHeight = 0;
	m_iNumElements = 0;

	m_bIsInited = true;

	return true;
}

template<typename K, typename V>
bool CBTree<K, V>::Insert(const K &key, const V &value)
{
	if(!m_bIsInited || Search(key) != NULL)
		return false;

	CBTreeNode<K, V> *pNewLeaf = new CBTreeNode<K, V>(key, value);
	CBTreeNode<K, V> *pNode = NULL;

	bool bDoUpdate = false;

	// --- Create rootnode and add initial element (if necessary) ---------- //
	if(!m_pRootNode) {
		m_pRootNode = new CBTreeNode<K, V>(key);

		pNewLeaf->SetParent(m_pRootNode);

		m_pRootNode->GetChildren()->push_back(pNewLeaf);

		m_iTreeHeight = 2;
		++m_iNumElements;

		return true;
	}

	// --- Add further element --------------------------------------------- //
	pNode = m_pRootNode;
	while(true)
	{
		if(pNode->GetChildren()->at(0)->m_bIsLeaf)
			break;

		for(int i=0; i<(int)pNode->GetChildren()->size(); ++i)
		{
			if(key < pNode->GetChildren()->at(i)->GetKey() || i == (int)pNode->GetChildren()->size()-1) {
				pNode = pNode->GetChildren()->at(i);
				break;
			}
		}
	}

	vector< CBTreeNode<K, V>* >::iterator it = pNode->GetChildren()->begin();
	for(; it<pNode->GetChildren()->end(); ++it)
		if(key < (*it)->GetKey())
			break;

	if(it == pNode->GetChildren()->end())
		bDoUpdate = true;

	pNewLeaf = new CBTreeNode<K, V>(key, value);
	pNewLeaf->SetParent(pNode);
	pNode->GetChildren()->insert(it, pNewLeaf);

	++m_iNumElements;

	// --- Update node keys (if necessary) --------------------------------- //
	if(bDoUpdate)
	{
		while(pNode && key > pNode->GetKey())
		{
			pNode->SetKey(key);
			pNode = pNode->GetParent();
		}
	}

	// --- Split (if necessary) -------------------------------------------- //
	pNode = pNewLeaf->GetParent();

	while((int)pNode->GetChildren()->size() > m_iMaxNodes)
	{
		const K oBiggestKey = pNode->GetChildren()->back()->GetKey();
		CBTreeNode<K, V> *pNewInnerNode = new CBTreeNode<K, V>(oBiggestKey);

		// Rootnode reached, so we gotta replace the old one.
		if(!pNode->GetParent())
		{
			m_pRootNode = new CBTreeNode<K, V>(oBiggestKey);
			m_pRootNode->GetChildren()->push_back(pNode);
			m_pRootNode->GetChildren()->push_back(pNewInnerNode);

			pNode->SetParent(m_pRootNode);

			++m_iTreeHeight;
		}
		// Else we need to place the new node at the correct position
		// of the parent.
		else
		{
			vector< CBTreeNode<K, V>* >::iterator it = pNode->GetParent()->
				GetChildren()->begin();
			for(; it<pNode->GetParent()->GetChildren()->end(); ++it)
				if(pNode->GetKey() == (*it)->GetKey())
					break;
			//if(it != pNode->GetParent()->GetChildren()->end())
				++it;
			pNode->GetParent()->GetChildren()->insert(it, pNewInnerNode);
		}

		// Set same parent as pNode
		pNewInnerNode->SetParent(pNode->GetParent());

		// Copy 2nd half of children to the new node and resize pNode
		int iNodesFrom = (int)pNode->GetChildren()->size() / 2;


		for(int i=iNodesFrom; i<(int)pNode->GetChildren()->size(); ++i) {
			pNode->GetChildren()->at(i)->SetParent(pNewInnerNode);
			pNewInnerNode->GetChildren()->
				push_back(pNode->GetChildren()->at(i));
		}

		pNode->GetChildren()->resize(iNodesFrom);
		pNode->SetKey(pNode->GetChildren()->at(iNodesFrom-1)->GetKey());

		pNode = pNode->GetParent();
	}		

	return true;
}

template<typename K, typename V>
bool CBTree<K, V>::Delete(const K &key)
{
	if(!m_bIsInited || !Search(key))
		return false;

	m_iTraverseHelper = -1;

	// --- Find the node and erase it -------------------------------------- //
	CBTreeNode<K, V> *pNode = m_pRootNode;

	while(true)
	{
		if(pNode->GetChildren()->at(0)->m_bIsLeaf)
			break;

		for(int i=0; i<(int)pNode->GetChildren()->size(); ++i)
			if(key <= pNode->GetChildren()->at(i)->GetKey()) {
				m_iTraverseHelper = i;
				pNode = pNode->GetChildren()->at(i);
				break;
			}
	}

	vector< CBTreeNode<K, V>* >::iterator it = pNode->GetChildren()->begin();
	int iDeleteHelper=0;
	for(; iDeleteHelper<(int)pNode->GetChildren()->size(); ++iDeleteHelper)
		if(key == pNode->GetChildren()->at(iDeleteHelper)->GetKey()) {
			delete pNode->GetChildren()->at(iDeleteHelper);
			break;
		}
	
	pNode->GetChildren()->erase(it+iDeleteHelper);
	--m_iNumElements;
	
	
	CBTreeNode<K, V> *pN = NULL;

	while((int)pNode->GetChildren()->size() < m_iMinNodes && pNode->GetParent())
	{
		bool bIsStealSuccessful = false;

		// --- Steal node from neighbour (if necessary) -------------------- //
		// Try to steal from right neighbour.
		if(m_iTraverseHelper<(int)pNode->GetParent()->GetChildren()->size()-1)
		{
			// Get right neighbour.
			pN = pNode->GetParent()->GetChildren()->at(m_iTraverseHelper+1);
			
			// Test whether the node is eligable for stealing.
			if((int)pN->GetChildren()->size() > m_iMinNodes)
			{
				pN->GetChildren()->at(0)->SetParent(pNode);
				pNode->GetChildren()->push_back(pN->GetChildren()->at(0));
				pNode->SetKey(pNode->GetChildren()->back()->GetKey());
				pN->GetChildren()->erase(pN->GetChildren()->begin());

				bIsStealSuccessful = true;
			}
		}
		// Try to steal from left neighbour.
		else if(m_iTraverseHelper > 0)
		{
			// Get left neighbour.
			pN = pNode->GetParent()->GetChildren()->at(m_iTraverseHelper-1);

			// Test whether the node is eligable for stealing.
			if((int)pN->GetChildren()->size() > m_iMinNodes)
			{
				pN->GetChildren()->back()->SetParent(pNode);
				pNode->GetChildren()->insert(pNode->GetChildren()->begin(),
											 pN->GetChildren()->back());
				pN->GetChildren()->resize(pN->GetChildren()->size()-1);
				pN->SetKey(pN->GetChildren()->back()->GetKey());				
			
				bIsStealSuccessful = true;
			}
		}

		// --- If stealing is not possible merge nodes --------------------- //
		if(!bIsStealSuccessful &&
			m_iTraverseHelper<(int)pNode->GetParent()->GetChildren()->size()-1)
		{
			// Get right neighbour.
			pN = pNode->GetParent()->GetChildren()->at(m_iTraverseHelper+1);
			
			// Copy over the children to their new parent :)
			for(int i=(int)pNode->GetChildren()->size()-1; i>=0; --i) {
				pNode->GetChildren()->at(i)->SetParent(pN);
				pN->GetChildren()->insert(pN->GetChildren()->begin(),
					pNode->GetChildren()->at(i));
			}
			
			pNode->GetParent()->GetChildren()->
				erase(pNode->GetParent()->GetChildren()->begin()+m_iTraverseHelper);
			delete pNode;
		}
		else if(!bIsStealSuccessful && m_iTraverseHelper > 0)
		{
			// Get left neighbour.
			pN = pNode->GetParent()->GetChildren()->at(m_iTraverseHelper-1);

			// Copy over the children to their new parent :)
			for(int i=0; i<(int)pNode->GetChildren()->size(); ++i)
			{
				pNode->GetChildren()->at(i)->SetParent(pN);
				pN->GetChildren()->push_back(pNode->GetChildren()->at(i));
			}

			pNode->GetParent()->GetChildren()->
				erase(pNode->GetParent()->GetChildren()->begin()+m_iTraverseHelper);
			delete pNode;

			K oNewKey = pN->GetChildren()->back()->GetKey();
			pNode = pN;
			while(oNewKey > pNode->GetKey() || key == pNode->GetKey())
			{
				pNode->SetKey(oNewKey);
				if(pNode->GetParent())
					pNode = pNode->GetParent();
				else
					break;
			}
		}

		pNode = pN->GetParent();

		if(pNode->GetParent()) {
			for(int i=0; i<(int)pNode->GetParent()->GetChildren()->size(); ++i)
				if(pNode->GetKey() == 
					pNode->GetParent()->GetChildren()->at(i)->GetKey()) {
					m_iTraverseHelper = i;
				}
		}
		else
		{
			if(pNode->GetChildren()->size() == 1) {
				--m_iTreeHeight;
				m_pRootNode = pNode->GetChildren()->at(0);
				m_pRootNode->SetParent(NULL);
				delete pNode;
				break;
			}
		}				

	} // while(true)

	if(m_pRootNode->GetChildren()->size() == 0) {
		delete m_pRootNode;
		m_pRootNode = NULL;
	}

	return true;
}

template<typename K, typename V>
V CBTree<K, V>::Search(const K &key) const
{
	if(!m_bIsInited || !m_pRootNode || key > m_pRootNode->GetKey())
		return NULL;

	CBTreeNode<K, V> *pNode = m_pRootNode;

	while(true)
	{
		if(pNode->GetChildren()->at(0)->m_bIsLeaf)
			break;

		for(int i=0; i<(int)pNode->GetChildren()->size(); ++i)
			if(key <= pNode->GetChildren()->at(i)->GetKey()) {
				pNode = pNode->GetChildren()->at(i);
				break;
			}
	}

	for(int i=0; i<(int)pNode->GetChildren()->size(); ++i)
		if(key == pNode->GetChildren()->at(i)->GetKey())
			return pNode->GetChildren()->at(i)->GetValue();

	return NULL;
}

#endif // __BTREE_H

// EOF
